Floyd- Warshall Algorithm Algorithm
The Floyd-Warshall algorithm is a graph analysis algorithm used for finding the shortest paths between all pairs of nodes in a weighted graph, allowing for the possibility of negative edge weights. This dynamic programming-based algorithm is efficient and highly effective in solving the all-pairs shortest path problem, making it widely used in various applications such as network routing protocols, network design optimization, and even in artificial intelligence for game level solving.
The algorithm operates by iteratively improving an estimate on the shortest path between two vertices, until the estimate is optimal. Initially, the shortest paths are assumed to be direct edges between the vertices, and the algorithm proceeds by updating these path lengths by considering intermediate vertices that may yield shorter paths. The algorithm successively examines all possible pairs of vertices and tests if the current shortest path between them can be improved by including another vertex as an intermediate point. This process is repeated for all vertices in the graph, eventually yielding the shortest path between every pair of vertices. The Floyd-Warshall algorithm is renowned for its simplicity and efficiency, having a time complexity of O(n^3), where n is the number of vertices in the graph.
/*
Petar 'PetarV' Velickovic
Algorithm: Floyd-Warshall Algorithm
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 300
#define INF 987654321
using namespace std;
typedef long long lld;
int n;
int dist[MAX_N][MAX_N];
int flojd[MAX_N][MAX_N];
//Floyd-Warshallov algoritam za trazenje duzina najkracih puteva svih parova cvorova u grafu
//Slozenost: O(V^3)
inline void FloydWarshall()
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
flojd[i][j] = dist[i][j];
}
flojd[i][i] = 0;
}
for (int k=1;k<=n;k++)
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
if (flojd[i][k] + flojd[k][j] < flojd[i][j])
{
flojd[i][j] = flojd[i][k] + flojd[k][j];
}
}
}
}
}
int main()
{
n = 3;
dist[1][1] = 0, dist[1][2] = 3, dist[1][3] = INF;
dist[2][1] = INF, dist[2][2] = 0, dist[2][3] = 4;
dist[3][1] = INF, dist[3][2] = 1, dist[3][3] = 0;
FloydWarshall();
printf("%d\n",flojd[1][3]);
return 0;
}
